#include <stdio.h>
#include <stdlib.h>

#define FNAME "/tmp/out"



struct node_st
{
	char data;
	struct node_st *l,*r;

};

struct node_st *tree = NULL;


int insert(struct node_st **root,int data)
{
	struct node_st *node;
	if((*root) == NULL)
	{
		node = malloc(sizeof(*node));
		if (node == NULL)
			return -1;

		node->data = data;
		node->l = NULL;
		node->r = NULL;

		(*root) = node;
		return 0;
	}
	

	if(data <= (*root)->data)/*左孩子*/
		return insert(&(*root)->l,data);
	return insert(&(*root)->r,data);/*右孩子*/

}

static void draw_(struct node_st *root,int level)
{
	int i = 0;
	if (root == NULL)
		return ;

	draw_(root->r,level+1);
	for (i = 0;i< level;i++)
		printf("	");
	printf("%c\n",root->data);
	draw_(root->l,level+1);
}

void draw(struct node_st *root)
{
	draw_(root,0);
	printf("\n\n");
}



static struct node_st *find_min(struct node_st *root)
{
	if (root->l == NULL)
		return root;
	return find_min(root->l);
}

static struct node_st *find_max(struct node_st *root)
{
	if (root->r == NULL)
		return root;
	return find_max(root->r);
}


static void turn_left(struct node_st **root)
{
	struct node_st *cur = *root;

	*root = cur ->r;
	cur->r = NULL;

	find_min(*root) ->l = cur;//找根结点的左子树 一直找到空 挂上
}

static void turn_right(struct node_st **root)
{
	struct node_st *cur = *root;

	*root = cur ->l;
	cur->l = NULL;

	find_max(*root) ->r = cur;
}

static int get_num(struct node_st *root)
{
	if (root == NULL)//叶子结点
		return 0;

	return get_num(root->l) + 1 + get_num(root->r); //计算左子树 + 根结点 + 右子树
}


void balance(struct node_st **root)
{
	if (*root == NULL)//叶子结点
		return ;
	int sub = 0;
	while(1)
	{

		sub = get_num((*root)->l) - get_num((*root)->r);//个数
	
		if (sub >= -1 && sub <= 1)//平衡
			break;
		if (sub < -1)// 右多
			turn_left(root);//左旋
		else
			turn_right(root);

	}//平衡完第一个根结点

	balance(&(*root)->l);//平衡左子树
	balance(&(*root)->r);//平衡右子树
}

void destroy(struct node_st *root)
{
	if (root == NULL)
		return ;
	destroy(root->r);
	destroy(root->l);
	free(root);
}

int save_(struct node_st *root,FILE *fp)
{
	fputc('(',fp);//写入(
	/*if error*/

	if(root ==  NULL)//空结点 写入)
	{
		fputc(')',fp);
		return 0;
	}

	fputc(root->data,fp);

	save_(root->l,fp);
	save_(root->r,fp);

	fputc(')',fp);
	/*if error*/
	return 0;
}

int save(struct node_st *root,const char *path)
{
	FILE *fp;
	fp = fopen(path,"w");
	if (fp == NULL)
		return -1;

	save_(tree,fp);
	return 0;
}



int main()
{
	char arr[] = "cefadjbh";
	int i =0;

	for (i = 0;i< sizeof(arr)/sizeof(*arr)-1;i++)//减去'\0'
	{
		insert(&tree,arr[i]);
	}

	draw(tree);
	save(tree,FNAME);
	exit(0);
}


